The present invention relates generally to management of concurrent transactions in a database, and more particularly, to systems and methods for reconciling concurrent streams of transactions in a scheduling database in such a manner that assures database integrity.
The fundamental purpose of a database is to execute transactions. A transaction is a unit of work that consists of a sequence of operations such as, read, write, update, and/or delete, against a database. A measure of the correctness of the state of the database is referred to as database integrity. Database integrity refers to the problem of ensuring that two or more concurrently executing transactions do not interfere with each other in such a manner as to produce an incorrect state in the database. An application programmer must ensure that each transaction produces a correct state, provided that each transaction begins when the database is in a correct state, and executes in isolation of all other transactions. For example, each transaction in an accounting application must leave assets balanced with liabilities and equity.
Interference among transactions can take many forms. One form of interference is the "lost-update" problem, which is illustrated in FIG. 1. As shown in FIG. 1, transaction A attempts to increment the value of field F in record R by 1. Concurrent with transaction A, transaction B attempts to multiply the value of field F by 2. At time t1, field F has a value of 4, and transaction A reads record R. At time t2, transaction B reads record R. At time t3, transaction A increments by 1 the value of field F that transaction A read at time t1 (i.e., 4 plus 1), and updates field F with the resulting value of 5. At time t4, transaction B multiplies by 2 the value of field F that transaction B read at time t2 (i.e., 4 multiplied by 2), and updates field F with the resulting value of 8. Transaction A's update to record R is lost in this example because transaction B overwrites field F at time t4 without considering that transaction A had changed the value of field F at time t3.
One known solution to the lost-update problem is to assign different execution priorities to each transaction. Specifically, a higher execution priority process P1 would take control over any computational resources that it would need to execute a transaction before a low priority process P2 executes its transaction. As a result, the two transactions have the effect on the database as if they arc each executed one at a time. The transaction in the low priority process must wait until the transaction in the high priority process completes its sequence of operations. In the example shown in FIG. 1, by assigning a high priority to a process that includes transaction A and a low priority to a process that includes transaction B, transaction B cannot read record R until after transaction A updates record R at time t3. By the time transaction B reads record R, the modification made by transaction A is reflected in record R, and thus, the lost-update problem is avoided.
However, assigning execution priority to each transaction does not guarantee "data priority," when multiple streams of transactions concurrently attempt to modify a database, where each stream may include several transactions. Even though each transaction in one stream may have execution priority over transactions in another stream, the transactions in the two streams may still interleave. In other words, a lower execution priority transaction can still overwrite the modifications in the database that were made by a higher execution priority transaction. Thus, when modifications of a higher priority stream conflict with the modifications of a lower priority stream, to assure data priority, the modifications of the higher priority stream are established in the database, whereas the modifications of the lower priority stream are not established in the database.
Hence, in the prior art database systems, the only way to ensure that a high priority stream of transactions acquires data priority over a low priority stream of transactions is to convert each stream into a single transaction. This ensures that the high priority stream executes completely before the low priority stream starts execution so that data priority holds when the high priority stream completes its execution. However, if the database entries that each stream attempts to modify are not known in advance, then each stream must acquire exclusive access to the entire database during execution in order to assure data priority over the other streams. Moreover, if streams have long execution times and if new streams of transactions arise over time, then each stream would have to wait an excessive amount of time in order to complete, which could cause blocking and deadlocks in the database.
Thus, it is desirable to have a method and system for reconciling in a database the execution of a first stream of transactions that is concurrent with a second stream of transactions such that the first stream has data priority over the second stream, and thus, ensuring database integrity without converting each stream into a single transaction.